package Test;

/**
 * \* Created with IntelliJ IDEA.
 * \* User: Administrator
 * \* Date: 2022/5/6
 * \* Time: 17:06
 * \* To change this template use File | Settings | File Templates.
 * \* Description:
 * \
 */
public class Demo2 {

    public static int getFirstUnFormedNum(int[] arr) {
        //找到[2,10]的范围
        int min = Integer.MAX_VALUE;
        int max = 0;
        for(int i: arr){
            min = Math.min(min,i);
            max += i;
        }

        boolean [] result = new boolean[max+1];
        result[0] = true;
        for (int i : arr){//遍历[3,2,5]
            for(int j = max; j >= i;j--){
                result[j] = result[j-i] || result[j];//如果result[j]为真，则更新为result[j-i]，否则维持原样
            }
        }
        for(int j =min; j < result.length;j++){
            if(!result[j]){
                return j ;
            }
        }
        return max+1;
    }

    public static void main(String[] args) {
        int[] value = {3, 2, 5};
        int[] weight = {3, 4, 5};
        getMaxValue(10, value, weight);
       // int t = getFirstUnFormedNum(arr);

    }

    public static void getMaxValue(int total, int[] value, int[] weight) {
        int m = total; //背包的最大容量
        int n = value.length; //商品个数

        //初始化物品价值矩阵
        int[][] arr = new int[n + 1][m + 1];

        for (int i = 0; i <= m; i++)
            arr[0][i] = 0;

        for (int j = 0; j <= n; j++)
            arr[j][0] = 0;

        //动态规划核心代码
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (weight[i - 1] <= j) {
                    if (arr[i - 1][j] < arr[i - 1][j - weight[i - 1]] + value[i - 1])
                        arr[i][j] = arr[i - 1][j - weight[i - 1]] + value[i - 1];
                    else
                        arr[i][j] = arr[i - 1][j];
                } else {
                    arr[i][j] = arr[i - 1][j];
                }
            }
        }
        //输出物品价值矩阵
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                System.out.print(arr[i][j]);
            }
            System.out.println();
        }
    }
}
